home *** CD-ROM | disk | FTP | other *** search
Text File | 1995-07-28 | 8.7 KB | 423 lines | [TEXT/MPS ] |
- /*
- File: RamTupleDatabase.cp
-
- Copyright: © 1991-1994 by Apple Computer, Inc.
- All rights reserved.
-
- Part of the AOCE Sample SMSAM Package. Consult the license
- which came with this software for your specific legal rights.
-
- */
-
-
-
- #ifndef __RAMTUPLEDATABASE__
- #include "RamTupleDatabase.h"
- #endif
-
- #ifndef __DEBUGASSERT__
- #include "DebugAssert.h"
- #endif
-
- #ifndef __DEBUGGINGGEAR__
- #include "DebuggingGear.h"
- #endif
-
- #ifndef __DEBUGCONSTANTS__
- #include "DebugConstants.h"
- #endif
-
- #ifndef __DIRECTOBJECT__
- #include "DirectObject.h"
- #endif
-
- #pragma segment ATupleDatabase
-
- class TDebugFlag;
- extern TDebugFlag chrisFlag;
-
- /***********************************|****************************************/
-
- class CTupleEntry : public TDirectObject
- {
- public: CTupleEntry ( const ATupleKey& key, const ADataItem& data, CTupleEntry* parent = nil );
- virtual ~CTupleEntry ();
-
- virtual ostream& operator >> ( ostream& s ) const;
-
- private: CTupleEntry ( const CTupleEntry& );
- CTupleEntry& operator = ( const CTupleEntry& );
-
- CTupleEntry* fParent;
- CTupleEntry* fLeft;
- CTupleEntry* fRight;
- unsigned long fIndex;
- CTupleKey fKey;
- CDataItem fData;
-
- friend class TRamTupleDatabase;
- };
-
- /***********************************|****************************************/
-
- CTupleEntry::CTupleEntry ( const ATupleKey& key, const ADataItem& data, CTupleEntry* parent ):
- fParent ( parent ),
- fLeft ( nil ),
- fRight ( nil ),
- fIndex ( 0 ),
- fKey ( key ),
- fData ( data )
- {
- }
-
- /***********************************|****************************************/
-
- CTupleEntry::~CTupleEntry ()
- {
- delete fLeft;
- delete fRight;
- }
-
- /***********************************|****************************************/
-
- ostream&
- CTupleEntry::operator >> ( ostream& s ) const
- {
- #if 1
- return s << "CTupleEntry: " << fKey << " " << fData << endl;
- #else
- s << "CTupleEntry @ " << (void*) this << '\n';
- s << "\tfParent: " << (void*) fParent << '\n';
- s << "\tfLeft: " << (void*) fLeft << '\n';
- s << "\tfRight: " << (void*) fRight << '\n';
- s << "\tfKey: " << fKey << '\n';
- s << "\tfData: " << fData << '\n';
- return s << "\tfIndex: " << fIndex << '\n';
- #endif
- }
-
- /***********************************|****************************************/
- /***********************************|****************************************/
-
- TRamTupleDatabase::TRamTupleDatabase ():
- ATupleDatabase (),
- fRoot ( nil ),
- fTupleCount ( 0 )
- {
- }
-
- /***********************************|****************************************/
-
- TRamTupleDatabase::~TRamTupleDatabase ()
- {
- delete fRoot;
- }
-
- /***********************************|****************************************/
-
- CTupleEntry*
- TRamTupleDatabase::FindTuple ( const ATupleKey& key ) const
- {
- CTupleEntry* tuple = fRoot;
-
- while ( tuple )
- {
- long relation = key.Compare ( tuple->fKey );
-
- if ( relation > 0 )
- tuple = tuple->fRight;
- else if ( relation < 0 )
- tuple = tuple->fLeft;
- else
- return tuple;
- }
-
- return tuple;
- }
-
- /***********************************|****************************************/
-
- CTupleEntry*&
- TRamTupleDatabase::FindTuple ( const ATupleKey& key, CTupleEntry*& parent ) const
- {
- parent = nil;
- CTupleEntry** tuple = (CTupleEntry**) &fRoot; // whoa-- this can't be right?pfl
-
- while ( *tuple )
- {
- long relation = key.Compare ( (*tuple)->fKey );
-
- if ( relation > 0 )
- {
- parent = *tuple;
- tuple = &(*tuple)->fRight;
- }
- else if ( relation < 0 )
- {
- parent = *tuple;
- tuple = &(*tuple)->fLeft;
- }
- else
- {
- break;
- }
- }
-
- return *tuple;
- }
-
- /***********************************|****************************************/
-
- Boolean
- TRamTupleDatabase::SetTuple ( const ATupleKey& key, const ADataItem& data )
- {
- CTupleEntry* parent;
- CTupleEntry*& tuple = FindTuple ( key, parent );
-
- if ( tuple )
- {
- tuple->fData = data;
- }
- else
- {
- tuple = new CTupleEntry ( key, data, parent );
-
- if ( tuple )
- {
- tuple->fIndex = ++fTupleCount;
- }
- }
-
- return tuple != nil;
- }
-
- /***********************************|****************************************/
-
- Boolean
- TRamTupleDatabase::GetTupleDataSize ( const ATupleKey& key, unsigned long& dataSize )
- {
- const CTupleEntry* tuple = FindTuple ( key );
-
- if ( tuple )
- {
- dataSize = tuple->fData.GetPhysicalLength ();
- return true;
- }
-
- return false;
- }
-
- /***********************************|****************************************/
-
- Boolean
- TRamTupleDatabase::GetTupleData ( unsigned long index, ADataItem& data )
- {
- const CTupleEntry* tuple = FindTuple ( index, fRoot );
-
- if ( tuple )
- {
- data = tuple->fData;
- return true;
- }
-
- return false;
- }
-
- /***********************************|****************************************/
-
- Boolean
- TRamTupleDatabase::GetTupleData ( const ATupleKey& key, ADataItem& data )
- {
- const CTupleEntry* tuple = FindTuple ( key );
-
- if ( tuple )
- {
- data = tuple->fData;
- return true;
- }
-
- return false;
- }
-
- /***********************************|****************************************/
-
- Boolean
- TRamTupleDatabase::DoesTupleExist ( const ATupleKey& key ) const
- {
- return FindTuple ( key ) != nil;
- }
-
- /***********************************|****************************************/
-
- Boolean
- TRamTupleDatabase::DeleteTuple ( const ATupleKey& key )
- {
- CTupleEntry* tuple = FindTuple ( key );
-
- if ( tuple )
- {
- // the scheme for deleting this node involves attaching our
- // right child subtree to our parent, and finding the node
- // to which our left child subtree should be attached to.
-
- CTupleEntry* parent = tuple->fParent;
-
- if ( parent )
- {
- // something is not right; our parent does not think we are its child
- ASSERT_RETURN_ZERO ( parent->fRight == tuple || parent->fLeft == tuple );
-
- CTupleEntry* leftSubtree = tuple->fLeft;
- CTupleEntry* rightSubtree = tuple->fRight;
-
- if ( parent->fLeft == tuple )
- parent->fLeft = rightSubtree;
- else if ( parent->fRight == tuple )
- parent->fRight = rightSubtree;
-
- if ( leftSubtree )
- {
- CTupleEntry*& leftAttach = FindTuple ( leftSubtree->fKey, parent );
-
- // theoretically we should always be reattaching our left
- // subtree to a nil leaf node pointer in some other node
- ASSERT_RETURN_ZERO ( leftAttach == nil );
-
- leftAttach = leftSubtree;
- }
- }
-
- tuple->fLeft = nil; // nil these out so the delete does not propogate
- tuple->fRight = nil; // nil these out so the delete does not propogate
- delete tuple;
- fTupleCount--;
- return true;
- }
-
- return false;
- }
-
- /***********************************|****************************************/
-
- unsigned long
- TRamTupleDatabase::CountTuples () const
- {
- return fTupleCount;
- }
-
- /***********************************|****************************************/
-
- Boolean
- TRamTupleDatabase::GetTuple ( unsigned long index, ATupleKey& key, ADataItem& data )
- {
- const CTupleEntry* tuple = FindTuple ( index, fRoot );
-
- if ( tuple )
- {
- key = tuple->fKey;
- data = tuple->fData;
- return true;
- }
-
- return false;
- }
-
- /***********************************|****************************************/
-
- CTupleEntry*
- TRamTupleDatabase::FindTuple ( unsigned long index, CTupleEntry* tuple ) const
- {
- if ( tuple )
- {
- if ( tuple->fIndex == index )
- return tuple;
-
- CTupleEntry* right = FindTuple ( index, tuple->fLeft );
-
- if ( right )
- return right;
-
- return FindTuple ( index, tuple->fRight );
- }
-
- return tuple;
- }
-
- /***********************************|****************************************/
-
- Boolean
- TRamTupleDatabase::GetTupleKey ( unsigned long index, ATupleKey& key )
- {
- const CTupleEntry* tuple = FindTuple ( index, fRoot );
-
- if ( tuple )
- {
- key = tuple->fKey;
- return true;
- }
-
- return false;
- }
-
- /***********************************|****************************************/
-
- Boolean
- TRamTupleDatabase::FindIndexOfTuple ( const ATupleKey& key, unsigned long& index ) const
- {
- CTupleEntry* entry = FindTuple ( key );
-
- if ( entry )
- {
- index = entry->fIndex;
- return true;
- }
-
- return false;
- }
-
- /***********************************|****************************************/
-
- Boolean
- TRamTupleDatabase::SetTuple ( unsigned long index, const ADataItem& data )
- {
- CTupleEntry* tuple = FindTuple ( index, fRoot );
-
- if ( tuple )
- {
- tuple->fData = data;
- return true;
- }
-
- return false;
- }
-
- /***********************************|****************************************/
-
- void
- TRamTupleDatabase::PrintSubtree ( ostream& s, const CTupleEntry* e ) const
- {
- if ( e )
- {
- PrintSubtree ( s, e->fLeft );
- s << e << '\n';
- PrintSubtree ( s, e->fRight );
- }
- }
-
- /***********************************|****************************************/
-
- ostream&
- TRamTupleDatabase::operator >> ( ostream& s ) const
- {
- s << "TRamTupleDatabase @ " << (void*) this << '\n';
- s << "\tfTupleCount: " << fTupleCount << '\n';
- s << "\tfRoot: " << (void*) fRoot << '\n';
-
- if ( chrisFlag.Flag ( kExtensiveTupleDBDescribe ) )
- PrintSubtree ( s, fRoot );
-
- return s;
- }
-
- /***********************************|****************************************/
-